// It is a CRC-CCITT implementation coded by David Qiu <david@davidqiu.com>
// Coder: David Qiu
// SNO: 11331262 
// Organization: School of Software, Sun Yat-Sen Univ.
// Date: 2013.10.15
//
// Info: 
//     CRC-CCITT Standard takes the G(x) as G(x) = x^16 + x^12 + x^5 + 1
// 
// Functions:
//     Use string to simulate the CRC-CCITT calculation procedure.

#include <iostream>
using namespace std;

string gx = "10001000000100001"; // The CRC g(x)
string msg; // The original message
string crc; // The CRC message

// Find the next position that starts with '1'
void nextPos(const string& reg, int& pos)
{
  for(;pos<reg.length();++pos)
    if(reg[pos]=='1')
      return;
}

// Modulo-2 Addition Division from specific index
void m2d(string& reg, int idx, const string& gx)
{
  for(int i=0;i<gx.length();++i)
  {
    reg[idx+i] = ( (reg[idx+i]==gx[i]) ? '0' : '1' );
  }
}

// Program entry
int main()
{
  // Input the original message
  cout << "Input the original message:" << endl;
  cin >> msg;
  
  // Check the input
  if(msg.length()==0)
  {
    cout << "[ERROR] Nothing to calculate." << endl;
    system("pause");
    return 0;
  }
  for(int i=0;i<msg.length();++i)
  {
    if(!(msg[i]=='0' || msg[i]=='1'))
    {
      cout << "[ERROR] Input format invalid." << endl;
      system("pause");
      return 0;
    }
  }
  
  // Process the CRC procedure
  string reg = msg;
  int pos = 0;
  nextPos(reg, pos);
  while(reg.length()-pos >= gx.length())
  {
    // Mod-2 Div
    m2d(reg, pos, gx);
    
    // Find the next position
    nextPos(reg, pos);
  }
  crc = reg.substr(pos);
  while(crc.length()<gx.length()-1) crc = "0" + crc;
  
  // Output the result
  cout << "Original Message: " << msg << endl;
  cout << "CCITT-CRC: " << crc << endl;
  system("pause");
  
  return 0;
}
